package com.linchong.dynamicprogramming.easy;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-18 12:40
 * @Description: LengthOfLIS$300-最长上升子序列-https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class LengthOfLIS {

	/**
	 * 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
	 *
	 * 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
	 *
	 *  
	 *
	 * 示例 1：
	 *
	 * 输入：nums = [1,3,5,4,7]
	 * 输出：3
	 * 解释：最长连续递增序列是 [1,3,5], 长度为3。
	 * 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence
	 *
	 *
	 * step 1: 确定状态
	 *  最后一步：对于最优的子策略，一定存在最后一个元素a[j]
	 *      第一种情况：最优策略中最长的连续上升子序列就是{a[j]},即答案是1，先考录最简单的情况
	 *      第二种情况：子序列的长度大于1，则最优策略中a[j]的前一个元素一定是a[j-1],这种情况下一定有，a[j]>a[j-1]
	 *      ... a[j-1] a[j]
	 *      因为是最优策略，所以该情况下，以a[j-1]结尾的连续上升子序列也一定是最长的
	 *  子问题：
	 *      本来是要求以a[j]结尾的最长上升子序列
	 *      转化为要求以a[j-1]结尾的最长连续上升子序列
	 *
	 *      转化为子问题
	 *  故状态：设f[j]=以a[j]结尾的最长连续上升子序列的长度
	 *
	 * step 2:转移方程
	 *      f[j] = 以a[j]结尾的最长连续上升子序列的长度
	 *          f[j] = max{1,f[j-1]+1|j>0 and a[j-1] < a[j] }
	 *          以a[j]结尾的最长连续上升子序列的长度=max{子序列就是a[j]本身，以a[j-1]结尾的最长连续上升子序列的长度+a[j]}
	 *          情况2满足j>0,即a[j]前至少有一个元素，a[j]>a[j-1],满足单调性
	 * step 3:初始条件空，边界同上
	 *
	 * step 4:计算顺序
	 *      f[j] = 以a[j]结尾的最长连续上升子序列的长度
	 *      计算f[0],f[1],f[2]...f[n-1]
	 *
	 *      注意
	 *          这里是n-1,坐标型，n个，0~(n-1)
	 *          不同于硬币组合，最终答案不一定是f[n-1],因为我们不知道最优策略中最后一个元素是那个a[j],所以答案是max{f[0],f[1],f[2]...,f[n-1]}
	 *
	 *      算法时间复杂度：O(n),空间复杂度：O(n)
	 *
	 *
	 *  【思考】空间复杂度如何变成O(1)
	 *
	 *
	 */
	public int lengthOfLIS(int[] nums) {

		int n = nums.length;
		int max= 1;
		if(n==0){
			return 0;
		}

		// 定义动态规划数组，保存状态
		int[] f = new int[n];

		// init
		f[0] = 1;

		for (int i = 1; i < n; i++) {
			f[i] = 1;
			if(nums[i]>nums[i-1]){
				f[i] = f[i-1]+1;
				if(f[i]>max){
					max = f[i];
				}
			}
		}
		return max;
	}
	public static void main(String[] args) {
		int[] nums = {10,9,2,5,3,7,101,18};
		LengthOfLIS instance = new LengthOfLIS();
		System.out.println(instance.lengthOfLIS(nums));
	}
}
